package com.wfm.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class PTwo07课程表{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int[] visited;
    boolean valid = true;// 是否无环
    List<List<Integer>> edge;
    boolean canFinish(int numCourse,int[][] preRequisites){
        visited = new int[numCourse];
        edge = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourse; i++) {
            edge.add(new ArrayList<>());
        }
        //边的指向：d[0] <-- d[1]
        for (int[] d:preRequisites) {
            edge.get(d[1]).add(d[0]);
        }
        for (int i = 0; i < numCourse&&valid; i++) {
            if(visited[i]==0){
                dfs(i);
            }
        }
        return valid;

    }
    // 0未搜素 1搜索中 2已完成
    void dfs(int u) {
        visited[u] = 1;
        for (int i = 0; i < edge.get(u).size(); i++) {
            int e = this.edge.get(u).get(i);
            if (visited[e] == 0) {
                dfs(e);
                if (!valid) {
                    return;
                }
            } else if (visited[e] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PTwo07课程表().new Solution();
    }
}